package com.monday.divide.and.conquer;

import lombok.AllArgsConstructor;
import lombok.Builder;
import lombok.Data;
import lombok.NoArgsConstructor;

import java.util.Arrays;

/**
 * 计算平台上最近的两个点
 * 二维平面上有 n 个点，如何快速计算出两个距离最近的点对？
 */
public class TwoClosestPoints {
    /**
     * 平面上最近的两个点
     * 1、将所有点按x轴排序, x轴相同的按y轴排序
     * 2、将最小的x值与最大的y值做一个矩形,矩形按x轴平分为左右两个矩形,假设分界线为 m
     * 3、计算左边矩形中最小值距离的d1, 计算右边矩形中小值距离为d2
     * 4、将原来分界线左边 x >= (m - min(d1,d2))的点与 右边 x <= (m + min(di,d2)) 点进行比较, 最小距离为d3
     * 5、最小距离是 min(d1,d2,d3)
     */

    public double twoClosestPoints(Point[] points) {
        System.out.println("初始点列表:" + Arrays.toString(points));
        Arrays.sort(points, (a, b) -> (a.x == b.x) ? (a.y - b.y) : (a.x - b.x));
        System.out.println("排序后列表:" + Arrays.toString(points));

        if (points.length < 2) {
            return -1;
        }

        return twoClosestPoints(points, 0, points.length - 1);
    }

    private double twoClosestPoints(Point[] points, int p, int r) {
        if (p >= r) {
            return Double.MAX_VALUE;
        }

        int q = (p + r) / 2;
        double k1 = twoClosestPoints(points, p , q);
        double k2 = twoClosestPoints(points, q + 1, r);
        double minLeftRight = Math.min(k1, k2);

        double k3 = twoClosestPoints(points, p, q, r, minLeftRight);

        return Math.min(minLeftRight, k3);
    }

    private double twoClosestPoints(Point[] points, int p, int q, int r, double minLeftRight) {
        double min = minLeftRight;

        for(int i = p; i <= q; i++) {
            // 剪枝：去掉 x < q - minLeftRight
            if (points[i].x < q - minLeftRight) {
                continue;
            }

            // 剪枝：去掉 x > q + minLeftRight
            for (int j = q + 1; j <= r; j++) {
                if (points[j].x > q + minLeftRight) {
                    continue;
                }

                double distance = points[i].distance(points[j]);
                min = Math.min(minLeftRight, distance);
            }
        }
        return min;
    }


    @Data
    @Builder
    @NoArgsConstructor
    @AllArgsConstructor
    public static class Point {
        private int x;
        private int y;

        @Override
        public String toString() {
            return "(" + this.x + "," + this.y + ")";
        }

        public double distance(Point p) {
            return Math.pow((Math.pow(this.x - p.x, 2) + Math.pow(this.y - p.y, 2)), 0.5);
        }

    }


}
